package com.hc.programming.array;

import com.hc.programming.util.ArrayUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 57.给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
 * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
 * 返回插入之后的 intervals。
 * 注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
 * <p>
 * 示例 1：
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出：[[1,5],[6,9]]
 * 示例 2：
 * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出：[[1,2],[3,10],[12,16]]
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 * <p>
 * 提示：
 * 0 <= intervals.length <= 10^4
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 10^5
 * intervals 根据 starti 按 升序 排列
 * newInterval.length == 2
 * 0 <= start <= end <= 10^5
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/7/11 22:06
 */
public class 插入区间 {
    public static void main(String[] args) {
        ArrayUtil.println(insert(new int[][]{{1, 5}}, new int[]{0, 0}));
        ArrayUtil.println(insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5}));
        ArrayUtil.println(insert(new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[]{4, 8}));
    }

    /**
     * 方案一：数组映射
     *
     * @param intervals   无重叠的已排序区间列表
     * @param newInterval 插入元素
     * @return 新数组
     */
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        // 找出最大值
        int max = newInterval[1];
        for (int[] a : intervals) {
            if (a[1] > max) {
                max = a[1];
            }
        }
        // 映射到数组
        int[] arr = new int[max * 2 + 2];
        for (int[] a : intervals) {
            arr[a[0] * 2]++;
            arr[a[1] * 2 + 1]--;
        }
        arr[newInterval[0] * 2]++;
        arr[newInterval[1] * 2 + 1]--;
        // 遍历找出数组对
        List<int[]> list = new ArrayList<>();
        int sum = 0;
        int start = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum > 0 && sum == arr[i]) {
                start = i;
            } else if (sum == 0 && arr[i] < 0) {
                list.add(new int[]{start / 2, (i - 1) / 2});
            }
        }
        return list.toArray(new int[list.size()][2]);
    }
}
